The world's technologies for communication, information and entertainment is steadily becoming digital. As part of this trend, still pictures are being stored and transmitted digitally; video is being transmitted and stored in digital form. Digital images and video together constitute an extremely important aspect of modem communication and information infrastructure. Efficient methods for processing multi-dimensional signals such as digital video and images are of deep technological significance. Examples of common application areas where such sophisticated processing is absolutely necessary include image and video compression for efficient video storage and delivery, manipulation of digital images and video frames for effective generation of artificial scenes, image or video enhancement etc.
Blurred Boundaries
Most digital images show objects delineated by boundaries which are not sharp. Boundaries can be considered as those regions between objects that indicate where one object ends and the next one begins. They help outline the various objects and help the eye distinguish and identify one object from another. In general, most visual images represented with pixels do not represent the boundaries as locations of sharp discontinuous changes in pixel values. The extent of an object would not normally end at one pixel with the adjacent object beginning the next pixel over. Instead of ending abruptly, the extent of one object disappears slowly into its neighbor and vice versa. Magnifying the image, one would see that the colors of adjacent objects bleed into each other across their edges. The extent over which this blending takes places gives the boundary a finite width and makes the boundaries appear fuzzy and spread out. Where one object starts and where its adjacent neighbor ends becomes less certain. The boundary between the two objects thus becomes wider. The width of the boundary is typically several pixels, five for example, but can vary from one pixel to ten or more. The widening of the boundaries has the effect of making the image look blurrier. The width of the boundaries can be used as a measure of the blurriness in the image.
Boundaries in an image can become blurry for several reasons. One reason is the finite resolution of the device used to record the image. The finite dimensions of the focussing optics and the granular or discrete nature of the recording media (grains in film or pixels in a CCD sensor) yield a certain resolving power that can distinguish between features of a certain size but no smaller. Features normally are not sharper or smaller than the resolving power of the recording device. Thus, edges and boundaries do not appear infinitely sharp but have a small but finite width instead. Another reason is the motion of objects. The recording media requires a finite amount of time to be exposed during which the object can move around. As the object moves, the edge of the object moves across the recording media yielding a wider boundary and a blurrier looking object. Blurry boundaries can also result from atmospheric disturbances (hot rising air, smoke, haze, etc.) that can diffuse the light from a single spatial point onto different areas in the recording media. Low contrast between the colors of adjacent objects and low light levels can also have the effect of blending the color of one object into the color of its adjacent object. Thus, images depicting realistic looking scenes tend to have blurry boundaries.
Video Compression
Although the field of the invention is not limited to video compression, in the context of video compression since a number of the same objects move around in a scene spanning several video frames, one attempts to create shortcuts for describing a current video frame being encoded or compressed in relation to other video frames that have already been transmitted or stored in the bit stream through a process of identification of portions of the current frame w/other portions of previously sent frames. This process is known as motion compensation. In technologies such a MPEG 1, 2 and 4 (in simple profile), the image frame is subdivided into square blocks that are then matched to a previously encoded frame and a displacement vector, also called motion vector, is placed in the bit stream indicating that the block in question should be replaced by the corresponding block in a previously encoded frame.
Such block-based motion compensation suffers from the limitation that the objects within most images are not built up of blocks. Such an attempt leads to poor matching and motion compensation. In particular blocks that traverse the boundary of two objects tend to have even poorer matches than others. Hence it becomes desirable to be able to directly manipulate the inherent constituent components in any given video frame, which are the objects or parts of objects, segments of arbitrary shapes (as allowed for instance in MPEG4 or as disclosed in “Method and Apparatus for Digital Image Segmentation,” International Publication Number WO 00/77735, applicant Pulsent Corporation, inventors A. Prakash, E. Ratner, J. S. Chen, and D. L. Cook, published Dec. 21, 2000) as the fundamental entities for use in motion compensation. Furthermore, applications such as artificial scene generation requires manipulation and placement of objects or segments in new locations. Image and video enhancement applications also need processing of the object segment.